The invention relates to an image display system and method, and in particular to an image display system that uses physical dynamic models to produce a realistic display of a scene.
It is becoming increasingly useful to display scenes on computer displays that represent the real world. Such scenes may occur in virtual reality devices, simulators and computer games.
One way of providing such scenes is to film images and to display the recorded images on the display. However, this approach requires that the content of the scene is predetermined and appropriate film sequences created and pre-stored in the computer. Thus, such an approach cannot be used where the scenes are not wholly scripted, which makes the approach unsuitable for simulations and computer games in which the user can carry out actions not predicted by the programmer.
An alternative approach uses a simulation of rigid body dynamics to allow scenes including such objects to be displayed realistically. In order to cope with simulation applications, the model has to be able to cope with a variable number of simulated objects that can be created and destroyed.
Such models should model a plurality of rigid objects that can interact with each other, subject to constraints. For example, if one object is hinged to another object that hinge acts as a constraint; the two objects cannot move independently. The existence of constraints makes the problem much more difficult to solve than a simple application of Newton's laws of motion.
A number of prior approaches have been presented but these have not proven wholly successful. The most suitable for simulation of multiple objects are so-called “extended coordinate methods” in which the constraints are introduced using Lagrange multipliers that correspond to forces that maintain the constraints. However, there are difficulties with these approaches.
Firstly, the known methods use a large number of variables, using nearly doubling the number of variables (because of the Lagrange multipliers) to describe the system, which results in them being eight times more computationally intensive than an equivalent system without constraints. Thus, the prior art methods tend to be highly inefficient.
Secondly, the known methods use differential algebraic equations that are numerically rather stiff. Simple methods for solving such equations are rather unstable.
Thirdly, it is not known how to efficiently incorporate friction into such systems. As will be appreciated, friction is an important property of real physical systems that has to be modelled correctly for a realistic result. This is a difficult problem but a working solution was reported in D. E. Stewart and J. C. Trinkle, “An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction”, International for numerical methods in engineering, volume 39 pages 2673-2691 (1996), and was improved on by Mihai Anitescu and F. A. Potra, “Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems”, Non-linear Dynamics, volume 14 pages 231-237 (1997). The approach described allows consistent models in which the velocities can always be computed and are always finite. The disadvantage of the approach is that the model involves solving a particular class of linear complementarity problem which has a structure such that not all algorithms are suitable. Anitescu and Trinkle used the Lemke algorithm but this is inefficient and prone to large errors.
A fourth difficulty with prior art approaches is that the constraints are generated automatically; such constraints need not be not independent of one another which results in the system being degenerate. Geometric analysis software that performs collision detection cannot check whether all the constraints are truly independent of each other, and only during simulation can it be determined that some constraints are redundant. Such degeneracy can cause real problems for the simulations, especially in the case of collision detection which checks for proximity of pairs of objects, whereas the constraint degeneracy only appears at the system level including all the rigid bodies in the system.
Fifthly, known systems do not cope well with stiffness, i.e. rigid spring-like systems and compliant elements. The only tractable solutions ignore contact and friction altogether, which makes them unsuitable for analysis of arbitrary physical systems.
Accordingly, there is a need for an image display system that ameliorates or alleviates some or all of these difficulties.
The known models require the solution of linear complementarity problems, a particular type of constrained equation. In general, a linear complementarity problem can be put in the form:Mz+q=w  (1)zi≧0 ∀iε{1, 2 . . . n}  (2)wi≧0 ∀iε{1, 2 . . . n}  (3)xiwi=0 ∀iε{1, 2 . . . n}  (4)
where M is an n by n matrix and z and w are real n-dimensional vectors. The problem requires finding the solution of equation (1), i.e. the values of z and w, subject to the constraints (2)-(4).
This is fundamentally a combinatorial problems, and solutions generally search through two index sets, where each index is in one of the sets. The first set a is a set of active variables for which wi=0 and the second set β is a set of free variables for which zi=0. The problem is then partitioned as
                                                        [                                                                                          M                      αα                                                                                                  M                      αβ                                                                                                                                  M                      βα                                                                                                  M                      ββ                                                                                  ]                        ⁡                          [                                                                                          z                      α                                                                                                            0                                                              ]                                +                      [                                                                                q                    α                                                                                                                    q                    β                                                                        ]                          =                  [                                                    0                                                                                      w                  β                                                              ]                                    (        5        )            where α and β specify indices in the first and second sets respectively.
This is equivalent to the linear algebra problemMααzα=−qαwβ=Mβαzα+q  (6)which must be solved for z while w is calculated by substitution. Mαα is known as the principal submatrix.
Various implementations are known. They differ in how the two sets are revised. They use a computed complementarity point which is a vector s such that
                              s          i                =                  {                                                                      z                  i                                                                              ∀                                      i                    ∈                    α                                                                                                                        w                  i                                                                              ∀                                      i                    ∈                    β                                                                                                          (        7        )            The methods go through a sequence of sets until a solution is found, i.e. until si≧0 ∀iε{1, 2 . . . n}
The Murty principal pivoting algorithm is known from Murty and Yu: “Linear Complementarily, Linear and Non Linear programming” available at
www.personal.engin.umich.edu/˜murty/book/LCPbook/index.html,
and also in an earlier edition published by Helderman-Verlag, Heidelberg (1988), the content of which is incorporated into this specification by reference.
The indices are assigned to a set, and i is set to zero. Then, the principal submatrix Mαα is formed and solved for z using equation (6).
Then s(i)=zα+wβ is calculated, wherewβ=Mβαzα  (8)If s≧0 then the algorithm has found a solution. Otherwise, the smallest index j for which the corresponding element of s is found. If this index is in the first set, the index is moved to the second, otherwise the index is in the second set in which case it is moved to the first set. The loop parameter i is incremented and the loop restarted until a solution is found.
The method is illustrated in the flow chart of FIG. 1.
The method is stateless and can be started from any initial guess for the division of the indices into first and second sets. The matrix will work on any P matrix and in particular on any positive definite matrix.
The method can fail where the matrix is positive semi-definite. Such matrices arise in real physical systems, and can be made positive definite by adding a small amount to each element along the diagonal. Kostreva in “Generalisation of Murty's direct algorithm to linear and convex quadratic programming”, Journal of optimisation theory and applications, Vol. 62 pp 63-76 (1989) demonstrated how to solve such positive semi-definite problems. Basically, the problem is solved for an initial value of ε, ε is then reduced until the solutions converge; if the solutions diverge the problem is unfeasible.